public class Sort {
    /*
    时间复杂度：最好是O(n)
    最坏是O(n^2)
    空间复杂度是O(n)
    最好是初始数组有序
     */
    public static void insertSort(int[] array) {
        for (int i = 1;i < array.length;i++) {
            int tmp = array[i];
            int j = i -1;
            for (;j >= 0;j--) {
                if (array[j] > tmp) {
                    array[j + 1] = array[j];
                } else {
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }
    //选择排序
    public static void  sellectSort(int[] array) {
        for (int i = 0;i < array.length;i++) {
            int minIndex = i;
            for (int j = i + 1;j < array.length;j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            int tmp = array[i];
            array[i] = array[minIndex];
            array[minIndex] = tmp;
        }
    }
    //希尔排序
    public static void  shellSort(int[] array) {
        int gap = array.length;
        while (gap > 1) {
            gap /= 2;
            shell(array,gap);
        }
    }
    //对每组进行插入排序
    public static void shell(int[] array,int gap) {
        for (int i = gap;i < array.length;i++) {
            int tmp = array[i];
            int j = i - gap;
            for (;j >= 0;j-=gap) {
                if (array[j] > tmp) {
                    array[j + gap] = array[j];
                } else {
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }
}
